/**
      <one line to give the program's name and a brief idea of what it does.>
    Copyright (C) <2011>  <André Mendes de Oliveira Paiva>

    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program.  If not, see <http://www.gnu.org/licenses/>.
  
 */

package estrutura.lista;

import estrutura.EstruturaDados;
import estrutura.No;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.util.ArrayList;

public class ListaAdjacencia extends EstruturaDados {

    private NoListaAdjacencia vertices;
    private int qtdNo;
    
    public ListaAdjacencia(String nome, int qtdeNo) {
        super(nome, qtdeNo);
        this.qtdNo = 0;
    }
    public ListaAdjacencia(String nome) {
        this(nome, QTDE_MAX_NO);
    }

    public ListaAdjacencia(int qtdeNo) {
        this(NOME_ESTRUTURA_ANONIMA, qtdeNo);
    }

    public ListaAdjacencia() {
        this(NOME_ESTRUTURA_ANONIMA, QTDE_MAX_NO);
    }

    private int obterMaxId()
    {
        int maxId = 0;
        NoListaAdjacencia noAtual = this.vertices;
        while (noAtual != null)
        {
           if ( noAtual.getId() > maxId ){
               maxId = noAtual.getId();
           }
           noAtual = noAtual.getProximo();
        }
        return maxId;
    }
    public boolean inserirNo(String valor) {
        boolean ret = false;
        NoListaAdjacencia novoNo = new NoListaAdjacencia(this.obterMaxId()+1, valor);
        if (vertices == null ) /* é o primeiro Nó */
        {
           this.vertices = novoNo;
           ret = true;
        }
        else{ /* percorre a lista até o último nó e adiciona o novo nó no fim */
            NoListaAdjacencia noAnt   = this.vertices;
            NoListaAdjacencia noAtual = this.vertices.getProximo();
            while (noAtual != null)
            {
               noAnt   = noAtual;
               noAtual = noAtual.getProximo();
            }
            noAnt.setProximo(novoNo);
            ret = true;
        }
        if (ret) this.qtdNo++;
        return ret;
    }

    /* Otem um determinado no a partir do ID do Nó */
    public NoListaAdjacencia obterNo(int idNo) {

        NoListaAdjacencia noPesq = null;
        NoListaAdjacencia noAtual = this.vertices;
        while (noAtual != null)
        {
           if ( noAtual.getId() == idNo ){
               noPesq = noAtual;
               break;
           }
           noAtual = noAtual.getProximo();
        }
        return noPesq;
    }

    /* Obtem o indice de um determinado no a partir do ID do Nó */
    public int obterIndiceNo(int idNo) {
        int ind = -1;
        NoListaAdjacencia noAtual = this.vertices;
        while (noAtual != null)
        {
           if ( noAtual.getId() == idNo ){
               ind = noAtual.getId();
               break;
           }
           noAtual = noAtual.getProximo();
        }
        return ind;
    }

    /* Obtem o ID de um determinado no a partir do valor Nó */
    public int obterIdPorValor(String valor)
    {
       int id = -1;
       NoListaAdjacencia noAtual = this.vertices;
       while (noAtual != null)
       {
         if ( noAtual.getValor().equals(valor) ){
            id = noAtual.getId();
            break;
         }
           noAtual = noAtual.getProximo();
       }
       return id;
    }

    /* Obtem o Id do nó Origem,, ou seja o nó que não é destino de nenhum outro nó */
    public int obterIDNoOrigem()
    {
       int id = -1;
       boolean achou=false;
       NoListaAdjacencia noAtual = this.vertices;
       NoListaAdjacencia noPesq;
       while (noAtual != null)
       {
          noPesq = this.vertices;
          achou = false;
          while (noPesq != null){
             if (noPesq.obterAresta(noAtual.getId()) != null){
               achou = true;
               break;
             }
             noPesq = noPesq.getProximo();
          }
          if (!achou){
           id = noAtual.getId();
           break;
          }
          noAtual = noAtual.getProximo();
       }
       return id;
    }

    public ArestaLista obterAresta(int idNoOrigem, int idNoDestino) {
        ArestaLista aresta = null;
        NoListaAdjacencia noOrigem = this.obterNo(idNoOrigem);
        if (noOrigem != null) {
            aresta = noOrigem.obterAresta(idNoDestino);
        }
        noOrigem = null;
        return aresta;
    }

    public boolean inserirAresta(int idNoOrigem, int idNoDestino) {
        return inserirAresta(idNoOrigem, idNoDestino, null, 0);
    }

    public boolean inserirAresta(int idNoOrigem, int idNoDestino, Object rotulo) {
        return inserirAresta(idNoOrigem, idNoDestino, rotulo, 0);
    }

    public boolean inserirAresta(int idNoOrigem, int idNoDestino, Object rotulo, int peso) {
        /* verifia se existe aresta */
        boolean ret = false;
        NoListaAdjacencia noOrigem = this.obterNo(idNoOrigem);
        NoListaAdjacencia noDestino = this.obterNo(idNoDestino);
        if (noOrigem != null && noDestino != null) {
            ret = noOrigem.addAresta(noDestino, rotulo, peso);
        }
        noOrigem = null;
        noDestino = null;
        return ret;
    }

    public boolean inserirRotulo(int idNoOrigem, int idNoDestino, Object rotulo) {
        boolean ret = false;
        NoListaAdjacencia noOrigem = this.obterNo(idNoOrigem);
        if (noOrigem != null) {
            ret = noOrigem.addRotulo(idNoDestino, rotulo);
        }
        return ret;
    }

    public boolean excluirNo(int idNo) {
       boolean ret = false;
       if (this.vertices.getId() != idNo)
       {
          NoListaAdjacencia noAnt   = this.vertices;
          NoListaAdjacencia noAtual = this.vertices.getProximo();
          while (noAtual != null)
          {
            if (noAtual.getId() == idNo)
                break;
            noAnt   = noAtual;
            noAtual = noAtual.getProximo();
          }
          if (noAtual != null)
          {
              noAtual.removeAllAresta();
              noAnt.setProximo(noAtual.getProximo());
              this.excluirTodasArestasDestino(idNo);
              noAtual = null;
              ret = true;
          }
      } else {
           this.vertices.removeAllAresta();
           this.vertices = this.vertices.getProximo();
           ret = true;
       }
       if (ret) this.qtdNo--;
       return ret;
    }
    public boolean excluirTodasArestasDestino(int idNoDestino)
    {
      boolean ret = false;
      if (this.vertices != null)
      {
        NoListaAdjacencia noOrigem = this.vertices;
        while (noOrigem != null)
        {
          noOrigem.removeAresta(idNoDestino);
          noOrigem = noOrigem.getProximo();
        }
        ret = true;
      }
      return ret;
    }
    public boolean excluirAresta(int idNoOrigem, int idNoDestino) {
        /* verifia se existe aresta */
        boolean ret = false;
        NoListaAdjacencia noOrigem = this.obterNo(idNoOrigem);
        if (noOrigem != null) {
            ret = noOrigem.removeAresta(idNoDestino);
        }
        noOrigem = null;
        return ret;
    }
    @Override
    public boolean excluirTodasArestas(int idNo) {
        /* verifica se existe aresta */
        boolean ret = false;
        if (this.vertices != null)
        {
          NoListaAdjacencia noOrigem = this.obterNo(idNo);
          if (noOrigem != null) {
              ret = noOrigem.removeAllAresta();
          }
        }
        return ret;
    }
   @Override
    public boolean excluirRotulo(int idNoOrigem, int idNoDestino) {
        /* verifica se existe aresta */
        boolean ret = false;
        NoListaAdjacencia noOrigem = this.obterNo(idNoOrigem);
        if (noOrigem != null) {
            ret = noOrigem.removeRotulo(idNoDestino);
        }
        return ret;
    }
    @Override
    public void imprimir() {
       System.out.println(super.toString());
       NoListaAdjacencia noAtual = this.vertices;
       while (noAtual != null)
       {
          noAtual.imprimir();
          noAtual = noAtual.getProximo();
       }
    }

    public void imprimirNosVizinhos(int idNo) {
        NoListaAdjacencia no = this.obterNo(idNo);
        if (no != null)
          no.imprimir();
    }
    /* Retorna o idNoice da primeira Aresta encontrada ou -1 senão existir aresta*/
    public int obterIDPrimeiraAresta(int idNo) {
        int id = -1;
        NoListaAdjacencia no = this.obterNo(idNo);
        if (no != null) {
            id = no.getIDPrimeiraAresta();
        }
        return id;
    }

    /* Retorna o id da próxima Aresta encontrada ou -1 senão existir aresta*/
    @Override
    public int obterIDProximaAresta(int idNoOrigem, int idNoDestino) {
        int id = -1;
        NoListaAdjacencia noOrigem = this.obterNo(idNoOrigem);
        if (noOrigem != null) {
            id = noOrigem.getIDProximaAresta(idNoDestino);
        }
        return id;
    }

    /* Retorna o rotulo da ligação ou null senão não existir aresta*/
    public Object obterRotuloAresta(int idNoOrigem, int idNoDestino) {
        NoListaAdjacencia noOrigem = this.obterNo(idNoOrigem);
        if (noOrigem != null) {
            return noOrigem.getRotuloAresta(idNoDestino);
        }
        return null;
    }

    public boolean obterDadosArquivo(String arquivo)
    {
        boolean res = true;
        String linha;
        try
        {
          FileReader      fr = new FileReader(arquivo);
          BufferedReader  br = new BufferedReader(fr);
          String []nos;      /* vetor de nós, obtido a partir da 1ª linha do arquivo */
          String []arestas;  /* vetor de arestas, obtido a partir da 2ª linha do arquivo */
          /* Lê a primeira linha, contendo os nós */
          linha = br.readLine();
          if (linha != null)
          {
            nos =  linha.split(";");
            /* insere os nós */
            for(int i = 0; i < nos.length; i++)
            {
                if (!(nos[i].trim()).equals(""))
                  this.inserirNo(nos[i]);
            }
          }
          int indNoOrigem;
          /* Lê as arestas e inclui as mesmas no grafo */
          while ((linha = br.readLine()) != null)
          {
             arestas = linha.split(";");
             /* obtem o ID do nó de origem, a partir do valor do nó */
             indNoOrigem = (this.obterIdPorValor(arestas[0]));
             if (indNoOrigem != -1)
             {
                for(int i = 1; i < arestas.length; i++)
                {
                   /* Se o valor for 1, então é para criar a aresta */
                    if ((arestas[i].trim()).equals("1.0"))
                      this.inserirAresta(indNoOrigem, i);
                }
             }
          }
        }
        catch (Exception e)
        {
           System.out.println("Erro ao obter os dados do arquivo: " + e.getMessage());
           res = false;
        }
       return res;
    }
    public boolean gerarArquivoEstrutura(String arquivo)
    {
        boolean res = true;
        String linha="";
        try
        {
          FileWriter      fr = new FileWriter(arquivo);
          BufferedWriter  br = new BufferedWriter(fr);
          /* Lê os nós */
          NoListaAdjacencia no = this.vertices;
          while (no != null)
          {
            linha += ";" + no.getValor();
            no     = no.getProximo();
          }
          /* grava a primeira linha do arquivo com os nós */
          br.write(linha);
          no = null;
          /* Lê nó e verifica as conexões do mesmo */
          NoListaAdjacencia noAtual = this.vertices;
          NoListaAdjacencia noAresta;
          while (noAtual != null)
          {
             noAresta = this.vertices;
             linha = noAtual.getValor();
             while (noAresta != null){
               if (noAtual.obterAresta(noAresta.getId()) != null )
                 linha += ";" + "1.0";
               else
                 linha += ";" + "0";
               noAresta = noAresta.getProximo();
            }
            noAtual = noAtual.getProximo();
            /* grava linha de arestas do nó */
            br.write("\n");
            br.write(linha);
          }
          br.close();
        }
        catch (Exception e)
        {
           System.out.println("Erro ao gravar os dados no arquivo: " + e.getMessage());
           res = false;
        }
       return res;
    }
    /* Obtem o ID do nó Destino, ou seja o nó que não é origem de nenhum outro nó */
    public int obterIDNoDestino()
    {
       int id = -1;
       NoListaAdjacencia noAtual = this.vertices;
       while (noAtual != null)
       {
          if (noAtual.getIDPrimeiraAresta() == -1)
          {
              id = noAtual.getId();
              break;
          }
          noAtual = noAtual.getProximo();
       }
       return id;
    }

    public ArrayList<No> obterVertices() {
        ArrayList <No> listaNo = new ArrayList<No>();
        NoListaAdjacencia noAtual = this.vertices;
        while (noAtual != null)
        {
           listaNo.add(noAtual);
           noAtual = noAtual.getProximo();
        }
       return listaNo;
    }

    public ArrayList<No> obterNosVizinhos(int idNo)
    {
       NoLista no = this.obterNo(idNo);
       if (no != null)
           return no.obterNosVizinhos();
       else
           return null;
    }

    public No obterNoPorID(int idNo)
    {
       return this.obterNo(idNo);
    }
}
